package likou;

import java.util.*;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/01/13 09:52
 */
public class _684 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(
                findRedundantConnection(new int[][]{{7,8},{2,6},{2,8},{1,4},{9,10},{1,7},{3,9},{6,9},{3,5},{3,10}})
        ));
    }

    public static int[] findRedundantConnection(int[][] edges) {
        List<Set<Integer>> list = new ArrayList<>();
        int[] now = new int[edges.length+1];
        int[] daan = new int[0];
        Arrays.fill(now,-1);
        for (int[] edge : edges) {
            //需要找到并连接两个set
            if (now[edge[0]]!=-1&&now[edge[1]]!=-1){
                //如果在同一个里面则画圆成功
                if (now[edge[0]]==now[edge[1]]){
                    daan = edge;
                }else {
                    List<Set<Integer>> temp = new ArrayList<>();
                    Set<Integer> set1 = list.get(now[edge[0]]);
                    Set<Integer> set2 = list.get(now[edge[1]]);
                    set1.addAll(set2);
                    int di = 0;
                    for (int i=0;i<list.size();i++){
                        if (i==now[edge[0]]||i==now[edge[1]]){
                            di++;
                            continue;
                        }
                        if (di==0){
                            temp.add(list.get(i));
                        }else {
                            Set<Integer> set = list.get(i);
                            for (Integer integer:set){
                                now[integer]-=di;
                            }
                            temp.add(set);
                        }
                    }
                    list = temp;
                    list.add(set1);
                    for (Integer inta:set1){
                        now[inta] = list.size()-1;
                    }
                }
            }else if (now[edge[0]]!=-1||now[edge[1]]!=-1){
                //插入一个值到一个set
                int nowI = now[edge[0]]!=-1?edge[0]:edge[1];//当前已经存在的位置
                int nowIN = now[edge[0]]!=-1?edge[1]:edge[0];//准备存的值
                Set<Integer> set = list.get(now[nowI]);
                set.add(nowIN);
                list.remove(now[nowI]);
                list.add(set);
                for (int i=now[nowI];i<list.size();i++){
                    for (Integer inta:list.get(i)){
                        now[inta] = i;
                    }
                }
            }else {
                Set<Integer> set = new HashSet<>();
                set.add(edge[0]);
                set.add(edge[1]);
                list.add(set);
                now[edge[0]] = list.size()-1;
                now[edge[1]] = list.size()-1;
            }

        }
        return daan;
    }
}
